/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-11
 * Time: 22:03
 */
public class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        int len = arr.length;
        // dp[i] 表示 arr[0, i) 中满足条件的最短数组的长度
        int[] dp = new int[len+1];
        dp[0] = len + 1; // 表示 0 之前没有满足条件的连续数组
        int sum = 0;
        int min = len+1;
        // 使用双指针记录当前连续数组
        int left = 0;
        int right = 0;
        while (right < len) {
            sum += arr[right];
            while (sum > target) {
                // 和 超过了 target
                sum -= arr[left];
                left++;
            }
            if (sum == target) {
                int l = right-left+1; // 记录当前连续数组的长度
                // 假设当前数组是后半部分的数组, 那么就要加上 前半部分的数组
                min = Math.min(min, l + dp[left]);
                // 当前的最小值就是之前的最小值 与 当前值 中的较小值
                dp[right+1] = Math.min(dp[right], l);
            } else {
                dp[right+1] = dp[right];
            }
            right++;
        }
        return min > len ? -1 : min;
    }
}
